//////////////////////////////////////////////////////////////////////
//
// NO_SimpleHash.h: interface for the NO_SimpleHash class.
//
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
#ifndef NO_SIMPLEHASH_H
#define NO_SIMPLEHASH_H

//////////////////////////////////////////////////////////////////////////
#include "NO_HashFunction.h"

//////////////////////////////////////////////////////////////////////
// a simple hash class
//////////////////////////////////////////////////////////////////////
template< class Key, class Type, NO_UInt32 HashSize = 1279>
class NO_SimpleHash  
{
public:
	//////////////////////////////////////////////////////////////////////////
	typedef std::allocator<Type> Allocator;

	//////////////////////////////////////////////////////////////////////////
	// node class [3/14/2005]
	//////////////////////////////////////////////////////////////////////////
	class Node
	{
	public:
		//////////////////////////////////////////////////////////////////////////
		Node(void)	{}
		virtual ~Node(void)	{}

		//////////////////////////////////////////////////////////////////////////
		Type* data;
		Key key;
		NO_UInt32 hashID ;
		Node* next;
		Node* prev;
	};	

	//////////////////////////////////////////////////////////////////////////
	class const_iterator;

	//////////////////////////////////////////////////////////////////////////
	// iterator
	//////////////////////////////////////////////////////////////////////////
	class iterator
	{
	public:
		//////////////////////////////////////////////////////////////////////////
		iterator(void)					{}
		iterator(Node& rhs):node(&rhs)	{}
		~iterator(void)					{}

		//////////////////////////////////////////////////////////////////////////
		bool		operator!=	(const iterator& rhs) const {return this->node != rhs.node;}
		bool		operator==	(const iterator& rhs) const {return this->node == rhs.node;}
		bool		operator!	(void)				  const {return !(this->node);}
		iterator&	operator=	(const iterator& rhs)	{node = rhs.node; return *this;}
		iterator&	operator++	(void)					{node = node->next; return *this;}  // prefix ++
		iterator&	operator--	(void)					{node = node->prev; return *this;}  // prefix --
		Type*		operator->	(void)					{return node->data;}
		const Type*	operator->	(void) const			{return node->data;}
		Type&		operator*	(void)					{return *node->data;}
		const Type&	operator*	(void) const			{return *node->data;}

		//////////////////////////////////////////////////////////////////////////
		const Key&	getKey(void)	{return node->key;}
		Node*		getNode(void)	{return node;}

	private:
		//////////////////////////////////////////////////////////////////////////
		friend class NO_SimpleHash; 
		friend class const_iterator;

		//////////////////////////////////////////////////////////////////////////
		Node* node;
	};	

	//////////////////////////////////////////////////////////////////////////
	// const_iterator
	//////////////////////////////////////////////////////////////////////////
	class const_iterator
	{
	public:
		//////////////////////////////////////////////////////////////////////////
		const_iterator(void)								{}
		const_iterator(Node& rhs):node(&rhs)				{}
		~const_iterator(void)								{}
		const_iterator(const iterator& rhs):node(rhs.node)	{}

		//////////////////////////////////////////////////////////////////////////
		const Type&		operator*	(void) const			{return *node->data;}
		const Type*		operator->	(void) const			{return node->data;}
		const_iterator&	operator++	(void)					{node = node->next; return *this;}  // prefix ++
		const_iterator&	operator--	(void)					{node = node->prev; return *this;}  // prefix --
		bool			operator!=	(const const_iterator& rhs) const {return this->node != rhs.node;}
		bool			operator==	(const const_iterator& rhs) const {return this->node == rhs.node;}
		bool			operator!	(void)				  const {return !(this->node);}

		//////////////////////////////////////////////////////////////////////////
		const Key&	getKey(void)	{return node->key;}
		Node*		getNode(void)	{return node;}

	private:
		//////////////////////////////////////////////////////////////////////////
		friend class NO_SimpleHash; 

		//////////////////////////////////////////////////////////////////////////
		Node* node;
	};	

	//////////////////////////////////////////////////////////////////////////
	// con/destruction
	//////////////////////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////
	NO_SimpleHash()
	{
		for (int i =0;i<HashSize;i++){hash[i] = 0;} 
		first.next= &last; 
		last.prev = &first;
	}

	//////////////////////////////////////////////////////////////////////////
	virtual ~NO_SimpleHash()
	{
		Node* iter = first.next;
		Node* end = &last;
		while(iter != end)
		{
			Node* node = iter;
			iter = iter->next;
			allocator.destroy(node->data);
			allocator.deallocate(node->data,1);
			delete node;
		} 
	}

	//////////////////////////////////////////////////////////////////////////
	// modify
	//////////////////////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////
	iterator insert (Key& key, const Type& data)
	{
		if (find(key)!=end()){return last;}
		NO_UInt32 hashID = noGetHash(key)%HashSize;

		Node* node = new Node();
		node->hashID = hashID;
		node->data = allocator.allocate(1,node->data);
		allocator.construct(node->data,data);
		node->key = key;
		node->prev = 0;
		node->next = 0;

		if(hash[hashID]){hash[hashID]->prev=node;}
		node->next = hash[hashID];
		hash[hashID] = node;
		node->next = getNext(*node);
		node->next->prev = node;
		node->prev = getPrev(*node);
		node->prev->next = node;

		return *node;
	}
	
	//////////////////////////////////////////////////////////////////////////
	void erase (Key& key)
	{
		NO_UInt32 hashID = noGetHash(key)%HashSize;
		Node* node = hash[hashID];
		if(!node){return;}
		while(node->hashID==hashID)
		{
			if(node->key==key)
			{		
				node->next->prev = node->prev;
				node->prev->next = node->next;
				allocator.destroy(node->data);
				allocator.deallocate(node->data,1);
				if (hash[hashID]==node)
				{
					if(node->next==&last){hash[hashID]=0;}
					else if(node->next==hash[node->next->hashID]){hash[hashID]=0;}
					else{hash[hashID]=node->next;}
				}
				delete node;
				return;
			}
			node = node->next;
		}
	}

	//////////////////////////////////////////////////////////////////////////
	void erase (iterator& iter)
	{
		Node* node = iter.getNode();
		node->prev->next = node->next;
		node->next->prev = node->prev;
		allocator.destroy(node->data);
		allocator.deallocate(node->data,1);
		NO_UInt32 hashID = node->hashID;
		if (hash[hashID]==node)
		{
			if(node->next==&last){hash[hashID]=0;}
			else if(node->next==hash[node->next->hashID]){hash[hashID]=0;}
			else{hash[hashID]=node->next;}
		}
		delete node;
	}

	//////////////////////////////////////////////////////////////////////////
	// retrieve
	//////////////////////////////////////////////////////////////////////////
	
	//////////////////////////////////////////////////////////////////////////
	iterator find (const Key& key)
	{
		NO_UInt32 hashID = (noGetHash(key)%HashSize);
		Node* node = hash[hashID];
		if (!node){return last;}
		while (node->hashID == hashID&&node!=&last)
		{
			if (noKeyCompare<Key>(node->key,key)){return *node;}
			node = node->next;
		}
		return last;
	}

	//////////////////////////////////////////////////////////////////////////
	iterator end	(void){return last;}
	iterator begin	(void){return *first.next;}
	
private:
	//////////////////////////////////////////////////////////////////////////
	Node& getBegin (void)
	{
		NO_UInt32 hashID = 0;
		while (hashID<HashSize)
		{
			if (Node* node = hash[hashID]){return *node;}
			hashID++;
		}
		return last;
	}

	//////////////////////////////////////////////////////////////////////////
	Node* getNext (Node& iter)
	{
		if(iter.next){return iter.next;}

		NO_UInt32 hashID = (noGetHash(iter.key)%HashSize)+1;
		while (hashID<HashSize)
		{
			if (hash[hashID]){return hash[hashID];}
			hashID++;
		}

		return &last;
	}

	//////////////////////////////////////////////////////////////////////////
	Node* getPrev (Node& iter)
	{
		if(iter.prev){return iter.prev;}

		NO_UInt32 hashID = (noGetHash(iter.key)%HashSize)-1;
		while (hashID<HashSize)
		{
			if (hash[hashID])
			{
				Node* t = hash[hashID];
				while(t->next->hashID==hashID&&t->next!=&last){t = t->next;}
				return t;
			}
			hashID--;
		}

		return &first;
	}

	//////////////////////////////////////////////////////////////////////////
	Allocator allocator;
	Node* hash[HashSize];
	
	//////////////////////////////////////////////////////////////////////////
	Node last;
	Node first;
};

//////////////////////////////////////////////////////////////////////
// a hash class with integer key
//////////////////////////////////////////////////////////////////////
template<class Type, NO_UInt32 HashSize = 1279>
class NO_IntHash  
{
public:
	//////////////////////////////////////////////////////////////////////////
	typedef std::allocator<Type> Allocator;

	//////////////////////////////////////////////////////////////////////////
	// node class [3/14/2005]
	//////////////////////////////////////////////////////////////////////////
	class Node
	{
	public:
		//////////////////////////////////////////////////////////////////////////
		Node(void)			{}
		virtual ~Node(void)	{}

		//////////////////////////////////////////////////////////////////////////
		Type* data;
		NO_UInt32 key;
		NO_UInt32 hashID ;
		Node* next;
		Node* prev;
	};	

	//////////////////////////////////////////////////////////////////////////
	class const_iterator;

	//////////////////////////////////////////////////////////////////////////
	// iterator
	//////////////////////////////////////////////////////////////////////////
	class iterator
	{
	public:
		//////////////////////////////////////////////////////////////////////////
		iterator(void)					{}
		iterator(Node& rhs):node(&rhs)	{}
		~iterator(void)					{}

		//////////////////////////////////////////////////////////////////////////
		bool		operator!=	(const iterator& rhs) const	{return this->node != rhs.node;}
		bool		operator==	(const iterator& rhs) const	{return this->node == rhs.node;}
		bool		operator!	(void)				  const	{return !(this->node);}
		iterator&	operator=	(const iterator& rhs) 	{node = rhs.node; return *this;}
		iterator&	operator++	(void)					{node = node->next; return *this;}  // prefix ++
		iterator&	operator--	(void)					{node = node->prev; return *this;}  // prefix --
		Type*		operator->	(void)					{return node->data;}
		const Type*	operator->	(void) const			{return node->data;}
		Type&		operator*	(void)					{return *node->data;}
		const Type&	operator*	(void) const			{return *node->data;}

		//////////////////////////////////////////////////////////////////////////
		const NO_UInt32&	getKey(void)	{return node->key;}
		Node*				getNode(void)	{return node;}

	private:
		//////////////////////////////////////////////////////////////////////////
		friend class NO_IntHash; 
		friend class const_iterator;

		//////////////////////////////////////////////////////////////////////////
		Node* node;
	};	

	//////////////////////////////////////////////////////////////////////////
	// const_iterator
	//////////////////////////////////////////////////////////////////////////
	class const_iterator
	{
	public:
		//////////////////////////////////////////////////////////////////////////
		const_iterator(void)								{}
		const_iterator(Node& rhs):node(&rhs)				{}
		~const_iterator(void)								{}
		const_iterator(const iterator& rhs):node(rhs.node)	{}

		//////////////////////////////////////////////////////////////////////////
		const Type&		operator*	(void) const			{return *node->data;}
		const Type*		operator->	(void) const			{return node->data;}
		const_iterator&	operator++	(void)					{node = node->next; return *this;}  // prefix ++
		const_iterator&	operator--	(void)					{node = node->prev; return *this;}  // prefix --
		bool			operator!=	(const const_iterator& rhs) const {return this->node != rhs.node;}
		bool			operator==	(const const_iterator& rhs) const {return this->node == rhs.node;}
		bool			operator!	(void)				  const {return !(this->node);}

		//////////////////////////////////////////////////////////////////////////
		const NO_UInt32&	getKey(void)	{return node->key;}
		Node*				getNode(void)	{return node;}

		//////////////////////////////////////////////////////////////////////////
		Node* node;
	};	

	//////////////////////////////////////////////////////////////////////////
	// con/destruction
	//////////////////////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////
	NO_IntHash()
	{
		for (int i =0;i<HashSize;i++){hash[i] = 0;} 
		first.next= &last; 
		last.prev = &first;
	}

	//////////////////////////////////////////////////////////////////////////
	virtual ~NO_IntHash()
	{
		Node* iter = first.next;
		Node* end = &last;
		while(iter != end)
		{
			Node* node = iter;
			iter = iter->next;
			allocator.destroy(node->data);
			allocator.deallocate(node->data,1);
			delete node;
		} 
	}

	//////////////////////////////////////////////////////////////////////////
	// modify
	//////////////////////////////////////////////////////////////////////////

	//////////////////////////////////////////////////////////////////////////
	iterator insert (const NO_UInt32& key, const Type& data)
	{
		if (find(key)!=end()){return last;}
		NO_UInt32 hashID = key%HashSize;

		Node* node = new Node();
		node->hashID = hashID;
		node->data = allocator.allocate(1,node->data);
		allocator.construct(node->data,data);
		node->key = key;
		node->prev = 0;
		node->next = 0;

		if (hash[hashID]){hash[hashID]->prev=node;}
		node->next = hash[hashID];
		hash[hashID] = node;
		node->next = getNext(*node);
		node->next->prev = node;
		node->prev = getPrev(*node);
		node->prev->next = node;

		return *node;
	}
	
	//////////////////////////////////////////////////////////////////////////
	void erase (NO_UInt32& key)
	{
		NO_UInt32 hashID = key%HashSize;
		Node* node = hash[hashID];
		if(!node){return;}
		while (node->hashID==hashID)
		{
			if (node->key==key)
			{		
				node->prev->next = node->next;
				node->next->prev = node->prev;
				allocator.destroy(node->data);
				allocator.deallocate(node->data,1);
				if (hash[hashID]==node)
				{
					if(node->next==&last){hash[hashID]=0;}
					else if(node->next==hash[node->next->hashID]){hash[hashID]=0;}
					else{hash[hashID]=node->next;}
				}
				delete node;
				return;
			}
			node = node->next;
		}
	}

	//////////////////////////////////////////////////////////////////////////
	void erase (iterator& iter)
	{
		Node* node = iter.getNode();
		node->prev->next = node->next;
		node->next->prev = node->prev;
		allocator.destroy(node->data);
		allocator.deallocate(node->data,1);
		NO_UInt32 hashID = node->hashID;
		if (hash[hashID]==node)
		{
			if(node->next==&last){hash[hashID]=0;}
			else if(node->next==hash[node->next->hashID]){hash[hashID]=0;}
			else{hash[hashID]=node->next;}
		}
		delete node;
	}

	//////////////////////////////////////////////////////////////////////////
	// retrieve
	//////////////////////////////////////////////////////////////////////////
	
	//////////////////////////////////////////////////////////////////////////
	iterator find (const NO_UInt32& key)
	{
		NO_UInt32 hashID = key%HashSize;
		Node* node = hash[hashID];
		if(!node){return last;}
		while (node->hashID == hashID&&node!=&last)
		{
			if(node->key==key){return *node;}
			node = node->next;
		}
		return last;
	}

	//////////////////////////////////////////////////////////////////////////
	iterator end	(void){return last;}
	iterator begin	(void){return *first.next;}
	
private:
	//////////////////////////////////////////////////////////////////////////
	Node& getBegin (void)
	{
		NO_UInt32 hashID = 0;
		while (hashID<HashSize)
		{
			if (Node* node = hash[hashID]){return *node;}
			hashID++;
		}
		return last;
	}

	//////////////////////////////////////////////////////////////////////////
	Node* getNext (Node& iter)
	{
		if(iter.next){return iter.next;}

		NO_UInt32 hashID = (iter.key%HashSize)+1;
		while (hashID<HashSize)
		{
			if (hash[hashID]){return hash[hashID];}
			hashID++;
		}

		return &last;
	}

	//////////////////////////////////////////////////////////////////////////
	Node* getPrev (Node& iter)
	{
		if(iter.prev){return iter.prev;}

		NO_UInt32 hashID = (iter.key%HashSize)-1;
		while (hashID<HashSize)
		{
			if (hash[hashID])
			{
				Node* t = hash[hashID];
				while(t->next->hashID==hashID&&t->next!=&last){t = t->next;}
				return t;
			}
			hashID--;
		}

		return &first;
	}

	//////////////////////////////////////////////////////////////////////////
	Allocator allocator;
	Node* hash[HashSize];
	
	//////////////////////////////////////////////////////////////////////////
	Node last;
	Node first;
};

#endif 
